数论分块

前言(扯淡)

数论分块是莫比乌斯反演和某些数学题有时候会用到的一个玩意,也是属于那种知道就知道不知道就不知道的内容,现场推如果不知道具体形式感觉还是很难想出来的.这篇博客就尝试用肯定很不严谨的态度尝试"证明"一下相关的内容,实际上就是能在不借助其他信息的前提下能独立推出正确的结论这个目的.

数论分块

考虑求下面这个式子:

i=1nni\sum\limits_{i=1}^n \left\lfloor\frac{n}{i}\right\rfloor

数论分块的重要依据就是ni\left\lfloor\frac{n}{i}\right\rfloornn个值排成一列,呈单调下降趋势,且是一段一段的.因此可以推出每一段的左右区间各自在哪,并借助类似前缀和的想法快速求和.由于最多只有n\sqrt{n}级别的不同的数,因此只要求和部分是O(1)O(1)的,整个求和部分就是O(n)O(\sqrt{n})的.

复杂度证明

整个序列的不同的数的个数是n\sqrt{n}级别的
对于ii而言,有两种取值:
ini \leq \left\lfloor\sqrt{n} \right\rfloorni\left\lfloor\frac{n}{i}\right\rfloorn\left\lfloor\sqrt{n} \right\rfloor种取值.

i>ni > \left\lfloor\sqrt{n} \right\rfloorni\left\lfloor\frac{n}{i}\right\rfloor由于nin\left\lfloor\frac{n}{i}\right\rfloor \leq \left\lfloor\sqrt{n} \right\rfloor因此也只有n\sqrt{n}种取值.

综上,分段是n\sqrt{n}级的.

假定现在知道区间左端点是ll,要求右端点rr.也就是要找到一个最大的rr满足nl=nr\left\lfloor\frac{n}{l}\right\rfloor = \left\lfloor\frac{n}{r}\right\rfloor.

rr的取值结论是r=nnlr = \left\lfloor\frac{n}{\left\lfloor\frac{n}{l}\right\rfloor}\right\rfloor

取值证明

证明他是正确的还是比较容易的.
首先对于这段区间而言,其中每一个值都是nl\left\lfloor\frac{n}{l}\right\rfloor

r=nnlnnl<r+1r = \left\lfloor\frac{n}{\left\lfloor\frac{n}{l}\right\rfloor}\right\rfloor \leq \frac{n}{\left\lfloor\frac{n}{l}\right\rfloor} < r + 1
换一下位置可以得到:
{nlnrnr+1<nl\begin{cases}\left\lfloor\frac{n}{l}\right\rfloor \leq \frac{n}{r}\\\frac{n}{r+1} < \left\lfloor\frac{n}{l}\right\rfloor\end{cases}
这个结论即证明了rr就是右端点,右移一位就不满足.
对于初始的ll来说,他肯定起始于数列的开头,之后每一次都可以往后推rr已经更新ll的位置.便可以解决开头的问题了.

模板代码

int f(int n)
{
    int res = 0;
    for(int l = 1,r;l <= n;l = r + 1)
    {
        r = n / (n / l);
        res += (r - l + 1) * (n / l);
    }
    return res;
}

例题① [CQOI2007]余数求和

原题链接:luogu 2261
题目大意:
给定n,kn,k,计算:

G(n,k)=i=1nk%iG(n,k) = \sum\limits_{i=1}^n k\%i

思路

考虑变换形式:对于k%ik \% i来说,他等价于kkiik - \left\lfloor\frac{k}{i}\right\rfloor * i
进一步,原式=i=1nkkii= \sum\limits_{i=1}^n{k - \left\lfloor\frac{k}{i}\right\rfloor * i}其中kk是个常数,可以拿出来,因此继续化简得到nki=1nkiin*k - \sum\limits_{i=1}^n{\left\lfloor\frac{k}{i}\right\rfloor * i}.距离数列分块的形式还多了一个ii,对于求和的每一个单独的元素来说,ii就是一段等差数列求和的值.对于[l,r][l,r]这段区间,ii部分产生的贡献即(l+r)(rl+1)/2(l +r) * (r - l + 1) / 2再加上数论分块的部分即可.

代码

typedef long long ll;
#define int ll
int n,k;
int f(int n)
{
    int res = 0;
    for(int l = 1,r;l <= n;l = r + 1)
    {
		r = k / l ? min(k / (k / l),n) : n;
        res += (k / l) * (r + l) * (r - l + 1) / 2;
    }
    return res;
}
signed main()
{
	scanf("%lld%lld",&n,&k);
	int fres = f(n);
    printf("%lld",n * k - fres);
    return 0;
}